COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a64.tex[106,phy] \today\hfill}

\bigskip
\line{\bf Recurrence.\hfill}

The Fibonnacci numbers exemplify a common pattern of computation: when you
have a certain number of consecutive ones (two, in this case), you can
easily get the next one (by adding the two, in this case). If the $F↓0$
is~0 and $F↓1$ is~1, we continue 
$$\vcenter{\halign{$\rt{#}\qquad$&\lft{#}\cr
i&0 1 2 3 4 5 6 \phantom{1}7 \phantom{1}8 \phantom{1}9 10 11 \phantom{0}12\cr
F↓i&0 1 1 2 3 5 8 13 21 34 55 89 144\cr}}$$
In computing a particular number, it isn't necessary to keep all the numbers.
Instead, imagine a window over the series, just large enough to see three
consecutive numbers.


\figbox 2.5truein:

First we fill in the unknown number at {\tt C}, by {\tt C:=A+B}. Then we
get the effect of moving the window to the right, by moving the scene
behind it to the left:

\smallskip\halign{\qq\qq\lft{\tt #}\cr
A:=B;\cr
B:=C;\cr
(* C:=? *)\cr
I:=I+1\cr}

\smallskip \noindent
With initialization and appropriate iteration, we get this:

\smallskip\halign{\qq\qq\lft{\tt #}\cr
(* INITIALIZE *)\cr
READ(N);\cr
I:=0; A:=0; B:=1; (* C=? *)\cr
\noalign{\smallskip}
WHILE I<N DO\cr
\qq BEGIN\cr
\qq C:=A+B;\cr
\qq A:=B; B:=C: I:=I+1\cr
\qq END;\cr
WRITE(N,A) (* N AND F(N) *)\cr}

Another recurrence: if, in Morse code, a dot takes one second and a dash
takes three, how many sequences of dots and dashes will fit into an 
{\tt N}-second interval? Call it {\tt M(N)}.
$$\vcenter{\halign{\rt{\tt #}\qquad&\rt{\tt #}\qquad&\lft{#}\cr
I&M(I)\hfil\cr
\noalign{\smallskip}
0&1\cr
1&1\cr
2&1\cr
3&2&(--- and $\cdot\cdot\cdot$)\cr
4&3&(--- $\cdot$ and $\cdot\cdot\cdot\;\cdot$ make 
   {\tt 2=M(3)}; $\cdot$ --- makes {\tt 1=M(1)}\cr
5&4\cr
6&6\cr
7&9\cr
8&13\cr
9&19\cr
10&28\cr}}$$

\noindent
In general, {\tt M(I)=M(I-1)+M(I-3)} for {\tt I>=3}.
The iteration is

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        WHILE I<N DO
            BEGIN
            D:=A+C;
            A:=B; B:=C: C:=D;
            I:=I+1
            END
}

%\smallskip\noindent
%If we want to make something repeat, a recurrence can do it:

%\smallskip\halign{\qq\qq\lft{\tt #}\cr
%DAY1:='SUNDAY'; DAY2:='MONDAY';...;\cr
%\qq DAY7:='SATURDAY';\cr
%\noalign{\smallskip}
%FOR I:=1 TO N DO\cr
%\qq BEGIN\cr
%\qq WRITELN ('DATE=',I,'DAY OF WEEK=',DAY1);\cr
%\qq PAGE (* OF CALENDAR *);\cr
%\qq DAYS:=DAY1;\cr
%\qq DAY1:=DAY2: DAY2:=DAY3; ...; DAY7:=DAY8\cr
%\qq END\cr}



\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 26, 1984

\bye